package com.peng.leetcode.tree;

/**
 * AddOneRow
 *
 * 623. 在二叉树中增加一行
 *
 * @author: lupeng6
 * @create: 2021/1/28 11:11
 */
public class AddOneRow {

    public static void main(String[] args) {
        Integer[] arr  = {4, 2, 6, 3, 1, 5};
        TreeNode root = TreeMain.array2tree(arr);
        TreeNode newRoot = new AddOneRow().addOneRow(root, 1, 2);
        System.out.println(TreeMain.preOrder(newRoot));
    }


    public TreeNode addOneRow(TreeNode root, int v, int d) {
        if (root == null) {
            return null;
        }
        if (d == 1) {
            TreeNode newRoot = new TreeNode(v);
            newRoot.left = root;
            root = newRoot;
        } else {
            dfs(root, v, d, 1);
        }
        return root;
    }

    private static void dfs(TreeNode root, int v, int d, int currentLevel) {
        if (d - 1 == currentLevel) {
            TreeNode left = root.left;
            TreeNode right = root.right;

            TreeNode newL = new TreeNode(v);
            TreeNode newR = new TreeNode(v);

            root.left = newL;
            root.right = newR;
            newL.left = left;
            newR.right = right;
        } else {
            if (root.left != null) {
                dfs(root.left, v, d, currentLevel + 1);
            }
            if (root.right != null) {
                dfs(root.right, v, d, currentLevel + 1);
            }
        }
    }

}
